import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {

        String s1="cbaebabacd",s2 = "abc";
        Solution solution = new Solution();

        List<Integer> list = new ArrayList<>();
        list = solution.findAnagrams3(s1,s2);
        int n = list.size();
        for(int i = 0; i<n; i++){
            System.out.println(list.get(i));
        }
    }
}
class Solution {
    public List<Integer> findAnagrams3(String ss, String pp){
        List<Integer> list = new ArrayList<>();
        int left=0,right=0;

        int count = 0;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] hash1 = new int[26];//统计，p中不同字符的个数
        int[] hash2 = new int[26];//统计，s中不同字符的个数

        for(char ch:p){//统计，p中不同字符的个数
            hash1[ch-'a']++;
        }

        for(;right<s.length;right++){
            //进窗口
            int in = s[right]-'a';
            hash2[in]++;
                //维护count
            if(hash1[in]>=hash2[in]) count++;

            //判断（窗口是否大了）
            if((right-left+1)>p.length){
                //出窗口
                int out = s[left]-'a';
                    //维护count
                if(hash1[out]>=hash2[out]) count--;
                hash2[out]--;
                left++;//这句好像特别容易丢
            }

            //更新结果
            if(count==p.length){
                list.add(left);
            }

        }
        return list;


    }
    public List<Integer> findAnagrams2(String s, String p) {
        //
        int left = 0;
        int right = 0;
        int[] arrs1 = new int[26];
        int[] arrs2 = new int[26];
        int count = 0;//窗口内有效字符个数
        List<Integer> list = new ArrayList<Integer>();
        for(char ch : p.toCharArray()){
            arrs1[ch-'a']++;
        }

        for(;right<s.length();right++){

            //进窗口
            int index = s.charAt(right)-'a';
            arrs2[index]++;
            //进窗口后的维护
            //if((arrs1[s.charAt(right)-'a'])>=(arrs2[s.charAt(right)]-'a')){//有效
            //    count++;
            //}
            if(arrs1[index]>=arrs2[index]){
                count++;
            }

            //判断
            if(count == p.length()&&(right-left+1)==p.length()){
                list.add(left);

            }else if((right - left + 1)> p.length()){//窗口大了
                int x = s.charAt(left)-'a';
                if(arrs2[x]<=arrs1[x]){
                    count--;//计数有效字符个数，--
                }
                arrs2[x]--;
                left++;

                if(count == p.length()){//一定要记得这里出窗口之后再维护一下count并进行一下判断；（这里逻辑还是不够清晰，一会儿再写个清楚的。）
                    list.add(left);
                }
            }
            /*else{
                if(arrs2[index]<=arrs1[index]){
                    count--;//计数有效字符个数，--
                }
                arrs2[index]--;
                left++;
            }*/
        }



            return list;
    }
    public List<Integer> findAnagrams(String s, String p) {
        //
        int[] arrs1 = new int[26];
        int[] arrs2 = new int[26];

        List<Integer> list = new ArrayList<Integer>();

        int flag = 1;
        int count=0;

        for(char c : p.toCharArray()){
            arrs1[c - 'a']++;
        }

        int left = 0;
        int right = 0;
        for(right = 0 ; right < s.length() ; right++){
            flag = 1;
            //进窗口
            arrs2[s.charAt(right) - 'a']++;

            if(right-left+1 > p.length()){//判断
                //出窗口
                arrs2[s.charAt(left)-'a']--;
                left++;
            }

            //更新结果
            for(int i = 0; i < 26; i++){
                if(arrs1[i] != arrs2[i]){
                    flag = -1;
                    break;
                }
            }
            if(flag == 1){
                count++;
                list.add(left);
            }


        }
        return list;
    }

}
